package com.acwing.lc.part1;

/**
 * @author rkc
 * @date 2022/9/12 9:25
 */
public class LC31下一个排列 {

    public void nextPermutation(int[] nums) {
        int k = nums.length - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, nums.length - 1);
        } else {
            //在k后面找一个比nums[k - 1]大的最小的数
            int t = k;
            while (t < nums.length && nums[t] > nums[k - 1]) t++;
            int val = nums[t - 1];
            nums[t - 1] = nums[k - 1];
            nums[k - 1] = val;
            reverse(nums, k, nums.length - 1);
        }
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
            l++;
            r--;
        }
    }
}
